package 动态规划.组合求和系列;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 货币面值 {

	
	
	public static int[] solution(int arr[] ,int aim) {
		Map<Integer,Integer> map  = new HashMap<>();
		for(int i : arr) {
			if(map.containsKey(i))
				map.put(i, map.get(i) + 1);
			else 
				map.put(i, 1);
//			map.put(i,map.getOrDefault(i, 1));
		}
		int len = map.size();
		int nums[][] = new int [len][2];
		int i = 0;
		for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
			nums[i][0] = entry.getKey();  
			nums[i++][1] = entry.getValue();
		}
		
//		process();
//		for(int a[] : nums)
//			System.out.println(Arrays.toString(a));
		
		return new int [] {process(0,len,nums,aim),dp(nums,aim),dpFinal(nums,aim)};	
	}
	
	/**
	 *  细品 就会发现 ，虽然这里面 ，由for 循环的存在
	 *  但是这还是  二叉树 的暴力递归
	 */
	public static  int process(int index,int len,int nums[][],int rest) {
		if(rest == 0)
			return 1;
		if(index == len )
			return 0;
		int ans = 0;
		for(int count = 0; rest - nums[index][0] * count >= 0 && count <= nums[index][1]; count++) {
			ans += process(index + 1, len,nums,rest - nums[index][0] * count);
		}
		return ans;
	}
	
	//  版本 1
	public static int dp(int nums[][],int aim) {
		int N = nums.length;
		int dp [][] = new int [N + 1][aim + 1];
		
		// 这个 basecase  对结果的 影响 是很重要的 ，已经不只一次 忘了 写 dp[N][0] = 1; 
		
		dp[N][0] = 1;
		for(int index = N - 1;index >= 0; index--) {
			dp[index][0] = 1;
			for(int rest = 1;rest <= aim; rest++) {
				int ans = 0;
				for(int count = 0;rest - nums[index][0] * count >= 0 && count <= nums[index][1];count++) {
					ans += dp[index + 1][rest - nums[index][0] * count];
				}
				dp[index][rest] = ans;
			}
		}
		return dp[0][aim];
	}
	
	// 最终优化版本
	public static int dpFinal(int nums[][],int aim) {
		int N = nums.length;
		int dp [][] = new int [N + 1][aim + 1];
		dp[N][0] = 1;
		for(int index = N -1; index >= 0;index--) {
			dp[index][0] = 1;
			for(int rest = 1;rest <= aim ;rest++) {
//				int temp = rest - nums[index][0];
				dp[index][rest] = dp[index + 1][rest];
				int temp = rest - nums[index][0] * (nums[index][1] + 1);
				if(rest - nums[index][0] >= 0)
					dp[index][rest] += temp >= 0 ? dp[index][rest - nums[index][0]] - dp[index + 1][temp] :
						dp[index][rest - nums[index][0]];		
			}
		}
		return dp[0][aim];
	}
	
	
	
	// 先写多叉树   错误的实现 
	public static int processError(int index,int len,int nums[][],int rest) {
		if(rest == 0)
			return 1;
//		if(index == len)
//			return 0;
		int ans = 0;
//		int count = 1;
//		if(nums)
		for(int i = index;i < len;i++) {
			for(int count = 0; count <= nums[i][1] && rest - nums[i][0] >= 0;count++) {
//				if(rest - nums[i][0] >= 0)
					ans += process(i,len,nums,rest - nums[i][0] * count);
//				ans += process();				
			}
		}
		return ans; 
	}
	
	/*
	 采用 carl 的那种多种背包的 介绍的方式 ， 来写
	 就是 将 出现的次数  **展开** ， 又是一个 01 背包的问题
	 直接按照01 背包 来写 就行了！
	 但是 该题 不是 01 背包 问题
	 */
	public static int dp01(int[] nums,int rest){
		int len = nums.length;
		int[][] dp = new int[len + 1][rest + 1];
		dp[len][0] = 1;
		for(int index = len - 1;index >= 0;index--){
			dp[index][0] = 1;
			for(int x = 1;x <= rest;x++){
				dp[index][x] = dp[index + 1][x];
				if(x - nums[index] >= 0){
					dp[index][x] += dp[index + 1][x - nums[index]];
				}
			}
		}
		return dp[0][rest];
	}

	public static void main(String args[]) {
//		int arr[] = {1,1,2,2,2,1,1};
		int arr[] = {1,1,1,1};
		int aim = 3;
		System.out.println(Arrays.toString(solution(arr,aim)));
		System.out.println(dp01(arr,aim));
		System.out.println();
	}
	
	
	
	
}
